Papers with combinatorial optimization problem
A Formal Perspective on Byte-Pair Encoding (2023.findings-acl)
Copied to clipboard
| Challenge: | Byte-Pair Encoding (BPE) is a popular algorithm used for tokenizing data in NLP, but the underlying optimization problem that BPE seeks to solve has not yet been laid down. |
| Approach: | They propose an algorithm which is a 1/sigma*(1-e(-sigma))-approximation of an optimal merge sequence. |
| Outcome: | The proposed algorithm improves the runtime complexity from O(NM) to O(N log M) and the lower bound of the approximation is approx0.37. |
Learning to Retrieve Iteratively for In-Context Learning (2024.emnlp-main)
Copied to clipboard
Yunmo Chen, Tongfei Chen, Harsh Jhamtani, Patrick Xia, Richard Shin, Jason Eisner, Benjamin Van Durme
| Challenge: | In-context learning is a powerful tool for learning large language models. |
| Approach: | They propose an iterative retrieval framework that empowers retrievers to make iterable decisions through policy optimization. |
| Outcome: | The proposed framework outperforms existing methods on semantic parsing datasets with 4M additional parameters for state encoding. |
Word-level Textual Adversarial Attacking as Combinatorial Optimization (2020.acl-main)
Copied to clipboard
| Challenge: | Existing word-level attack models are far from perfect because of unsuitable search space reduction methods and inefficient optimization algorithms. |
| Approach: | They propose a novel adversarial adversarialist model that incorporates word substitution and particle swarm optimization to solve two problems separately. |
| Outcome: | The proposed model achieves much higher success rates and crafts more high-quality adversarial examples as compared to baseline methods. |
GAP: a Global Adaptive Pruning Method for Large Language Models (2025.emnlp-main)
Copied to clipboard
| Challenge: | Existing structured pruning methods employ uniform compression rates across network layers, neglecting the varying importance of different network depths. |
| Approach: | They propose a pruning framework that minimizes global capability loss by layer-adaptive pruning rates. |
| Outcome: | The proposed approach achieves comparable performance with state-of-the-art methods at high pruning rates and shows significant advantages at low pruning rates. |
JoPA: Explaining Large Language Model’s Generation via Joint Prompt Attribution (2025.acl-long)
Copied to clipboard
| Challenge: | Existing attempts to explain the entire language generation often treat input prompt texts independently, ignoring their combinatorial effects on the follow-up generation. |
| Approach: | They propose a framework for explaining how a few prompt texts collaboratively influences the LLM's complete generation. |
| Outcome: | The proposed explanations demonstrate faithfulness and efficiency of the proposed framework. |
Rethinking Word-level Adversarial Attack: The Trade-off between Efficiency, Effectiveness, and Imperceptibility (2024.lrec-main)
Copied to clipboard
| Challenge: | Neural language models have demonstrated impressive performance but remain vulnerable to word-level adversarial attacks. |
| Approach: | They propose two standardized search spaces to address the problem of word-level adversarial attacks. |
| Outcome: | The proposed search spaces improve performance and trade-offs in different scenarios. |